\section{Introduction}

Commercial ``Infrastructure as a Service'' clouds (i.e. {\em public
clouds}) often make use of commodity data center components to achieve the
best possible economies of scale.  In particular, large-scale e-commerce cloud
providers such as Google and Alibaba deploy ``converged'' components that
co-locate computing and storage in each hardware module (as opposed to having
separate computing and storage ``tiers.'')  The advantage of such an approach
is that all infrastructure components are used to support paying customers --
there are no resources specifically dedicated to cloud services.
%One of emerging architectures for building cloud services is a converged
%storage architecture that leverages commodity servers with software clustered
%storage.
%The converged architecture (server plus compute in same tier) grew out of the
%Google model. 
In particular, these providers use software to
aggregate multiple direct attached low-cost disks together across
servers as a way of avoiding the relatively high cost of network attached 
storage~\cite{googlefs03,hdfs10,NutanixPaper}.
%systems. %This(e.g. ~\cite{NutanixPaper}).  Leading cloud platform companies
%such as Google, Amazon, Alibaba, Microsoft Azure  have built a converged
%compute and storage infrastructure and used a distributed file system such as
%Google file system~\cite{googlefs03,hdfs10} to glue a large number of
%commodity servers.
% with local storage into a single cluster.
In such an environment,
%That  allows the use of scalable compute and storage, without incurring the
%costs and performance limitations associated with network storage.
each physical machine runs a number of virtual machines (VMs)
%as  instances of a guest operating system 
and their virtual disks are stored as disk image files.
% typically using a local (possibly shared) file system.
Frequent snapshot backup of virtual machine images can
increase the service reliability by allowing VMs to restart from their latest
snapshot in the event of a server failure. Snapshots contain highly redundant 
data chunks and 
%  However, because the disk
%blocks that make up the VMs are often the same from snapshot to snapshot
%and are shared among VMs,  
deduplication of redundant 
content~\cite{venti02,bottleneck08} is necessary to substantially reduce the
storage demand. 

%For example, the Aliyun cloud, which is  the largest cloud service provider
%by Alibaba in China, automatically conducts  the backup of virtual disk
%images to all active users every day.  The cost of supporting a large number
%of concurrent backup streams is high because of the huge storage demand and
%the use of deduplication

%Without deduplication,
Source-side deduplication~\cite{Vrable2009,Tan2010,Fu2014,Symantec2009}
eliminates duplicates before backup data is transmitted
to a secondary storage, which saves network bandwidth significantly; however its resource
usage can impact other co-located cloud services. 
It is memory-intensive to compare a large number of fingerprints and identify
duplicates, even with optimization or approximation techniques developed~\cite{Guo2011,Dong2011,extreme_binning09,FuFast2015}. 
\comments{
When deleting unused snapshots, a grouped mark-and-sweep approach~\cite{Guo2011}  
is effective while it still carries a significant cost, especially in a distributed
setting. 
} Another side effect of deduplication is the possible loss of failure
resilience~\cite{Reliability06}.  
%Separate files share the same physical copies of blocks that are
%logically duplicated among them.  
If a shared block is lost, all files that
share that block are affected.  
A cloud may offload backup workload from production 
server hosts to dedicated backup proxy servers (e.g. EMC Data Domain) or
backup services (e.g. Amazon S3). This approach simplifies the cluster 
architecture and 
avoids potential performance degradation to production applications when 
backups are in progress.
However, sending out raw and undeduplicated backup data wastes a huge amount
of network bandwidth that would otherwise be available to user VMs. 
\comments{
Even when the storage system implements deduplication internally
such dedicated backup storage is either difficult to scale out
(which can comprise the overall scalability of the converged architecture) 
or it must forego global deduplication in order to gain scalability 
(which increases backup cost).
}

\IEEEpubidadjcol
Our work  considers a backup service with source-side deduplication for converged cloud architectures
that is co-located with user VMs, sharing the cloud compute, network, and
storage resource with them.  
This paper extends our preliminary simulation study~\cite{WeiZhangIEEE} to 
restrict the scope of cross-VM deduplication and simplify the deduplication process
by separating popular data chunks and presents the design and implementation of 
a VM-centric backup scheme.  
We term this approach {\em VM-centric} because the deduplication
algorithm considers VM boundaries in making its decisions as opposed to
treating all blocks as being equivalent within the storage system.
Our work focuses on a tradeoff that allows the sharing of only ``popular'' data blocks 
across virtual machines while using localized deduplication within each VM
to achieve both storage savings and fault isolation.
Another issue addressed is fault  isolation in a content sharing environment caused by deduplication.
One consequence of aggressive deduplication is the possible loss of failure
resilience.  If a shared block is lost, all files that
share that block are affected~\cite{Reliability06} and  our work is motivated by this
to develop VM-centric fault isolation techniques.
\comments{
Since the underlying storage file system block size is typically bigger than the average data chunk size
used for deduplication,  packaging
content from different VMs into the same file block  creates a ``false'' sharing that 
affects fault isolation;
}


The main contribution of this paper is
1) a design and implementation of a backup service 
to integrate the VM-centric techniques while minimizing the resource impact on other 
collocated cloud services;
2) a VM-centric file block management to improve snapshot availability by
separating popular chunk replication and
packaging data chunks from the same VM into a file system block as much as possible; 
3) an analysis on the deduplication efficiency by using popular items
and also on snapshot availability improved by the above fault isolation design. 
The analysis provides insights and justification on the proposed VM-centric strategies.
The integrated optimization includes  similarity-guided local deduplication for
each VM to make the overall deduplication efficiency more competitive 
to a traditional deduplication scheme.
Our  experimental study compares  the VM-centric approach with the previous 
VM-oblivious approaches in terms of deduplication efficiency, resource usage,  and snapshot availability.
Compared to our earlier study~\cite{WeiZhangIEEE} which achieves 92\% of what the full deduplication
can do, our integrated system delivers over  96\% in a tested dataset from Alibaba cloud. 
%Thus we improve  to avoid such VM-oblivious packaging.
%our approach uses a deduplication data chunk size that is smaller than a
%single file block and

 
%Deduplicating
%data locally within a VM also reduces the need to maintain a global index of
%chunks that are shared among VMs, thereby increasing the scaling efficiency of
%the snapshot system.  


\comments{
The key contribution of this work is a set of methodologies to address the following two challenges:
1) simple deduplication and snapshot deletion with competitive efficiency and 
a small resource usage without affecting other collocated cloud services;
2) improved fault isolation for the sharing of deduplicated data,
given that node failures in converged architecture are the norm rather than
exception.

Version-based detection has been used to identify file blocks that have not
changed across snapshots so their redundant storage can be
avoided~\cite{Clements2009,Vrable2009,TanIPDPS2011}.
%the previous version of the
%snapshot~\cite{Clements2009,Vrable2009,TanIPDPS2011}, 
Alternatively, techniques that compare block ``fingerprints'' to
identify duplicates
that exist among all files regardless of their 
origin~\cite{Guo2011,Dong2011,extreme_binning09} have
also gained in popularity.  
One consequence of aggressive deduplication is the possible loss of failure
resilience.  Separate files share the same physical copies of blocks that are
logically duplicated among them.  If a shared block is lost, all files that
share that block are affected.  
Thus, there exists a
tension between the additional redundancy that snapshot creation is intended
to provide, and the storage efficiency that deduplication makes possible.
The previous work on deduplication has not considered the impact of 
duplicate sharing on  fault tolerance.
} 
\comments{
We detail the storage, performance, and fault isolation properties
of our method and verify these properties empirically using a prototype
system that we have developed to run as a co-located back-up service in
converged IaaS cloud environments.

%, and to propose a VM-centric approach that localizes
%deduplication as much as possible and restricts global deduplication only to a
%limited set of most popular blocks.  
%In our method, local deduplication uses
%similarity-guided elimination to improve the deduplication coverage.  
Since the underlying storage file system block size is typically bigger than the average data chunk size
used for deduplication,  packaging
content from different VMs into the same file block  creates a ``false'' sharing that 
affects fault isolation. Thus we choose to avoid such VM-oblivious packaging.
%our approach uses a deduplication data chunk size that is smaller than a
%single file block and
%Thus our strategy is to packages data chunks from the same VM into a file
%system block as much as possible to improve fault isolation.  
%Deduplicating
%data locally within a VM also reduces the need to maintain a global index of
%chunks that are shared among VMs, thereby increasing the scaling efficiency of
%the snapshot system.  
The cost associated with localization, however, is in 
the lost
storage efficiency that cross-VM deduplication makes possible.  To recover
some of this efficiency we allow a small number of the most popular data
blocks to be deduplicated (and then replicated) across VMs.  
}

%Because data
%sharing is restricted, this VM-centric approach reduces the overall resource
%usage significantly during backup and simplifies the snapshot deletion
%process. This low-resource design is suitable when the backup service with
%deduplication is co-located with other services running on a shared compute
%and storage cluster.  We have evaluated this VM-centric approach using  a
%prototype system.
% that runs a cluster of Linux machines with Xen and a standard distributed
% file system for the backup storage. 
%This approach localizes duplicate detection within each VM  By narrowing
%duplicate sharing within a small percent of common data chunks and exploiting
%their popularity, this scheme can afford to allocate extra replicas of these
%shared chunks for better fault resilience while sustaining competitive
%deduplication efficiency.

%In addition, our VM-centric design allows garbage collection to be performed in a localized
%scope and we propose an approximate deletion scheme to reduce this cost further.
%Localization also brings the benefits of greater ability to exploit parallelism so
%backup operations can run simultaneously without a central  bottleneck.
%This VM-centric solution uses a small amount of  memory while delivering reasonable deduplication efficiency. 

%Another issue considered is that
%that garbage collection after deletion of old snapshots also competes for computing resources. 
%Sharing of data chunks among by multiple VMs needs to be detected during
%garbage collection and such dependencies complicate deletion operations. 

%************** Paper sections summary
%THIS NEEDS MODIFICATION


The rest of this paper is organized as follows.
Section~\ref{sect:background} reviews the background and discusses the  design options for snapshot backup 
with a VM-centric approach. 
%Section~\ref{sect:deduplication}  analyzes the tradeoff and benefits of the VM-centric approach. 
Section~\ref{sect:deduplication}  presents our scheme for  snapshot deduplication. 
%and deletion.
Section~\ref{sect:architecture}  describes a system implementation that evaluates the proposed techniques.
%   the benefit of our approach for fault isolation. 
Section~\ref{sect:evaluation} is our experimental evaluation that compares with other approaches.
Section~\ref{sect:conclusion}  concludes this paper.
The appendix describes an analysis on the deduplication  efficiency with top $k$ popular chunks. 
